/**
 * 删除链表的倒数第 N个节点
 *
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 * 示例 1：
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 *
 * 示例 2：
 * 输入：head = [1], n = 1
 * 输出：[]
 *
 * 示例 3：
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 */

/**
 * 碰到节点的题目一定要记得我们要自己定义一个新的节点, 让他的 next 指向 题目中链表的 head 节点, 这样在后面的返回值, 和重新初始化会简单很多
 *
 * 1. 这题实际上非常简单, 只需要扫描两趟就可以了, 第一趟扫描出整个节点数, 第二趟就可以直接定位到要删除的节点位置,
 * 后面就正常删除节点就可以了
 * 时间复杂度 : O(n^2)
 * 空间复杂度 : O(1)
 *
 * 官方解法 :
 * 2. 但是这题有种进阶写法, 就是如何用一趟扫描就完成节点的删除
 * 我们其实并不需要求出整个链表的长度, 我们要删除倒数第 n 个节点, 也就是 要删除的节点离最后一个节点之间的距离为 n - 1
 * 我们完全可以用 两个节点 一起来遍历, 只要慢的节点距离快的节点的距离也是 n - 1, 那当快的指针走到最后一个位置时, 慢的节点
 * 也就是我们需要的位置了
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */


public class Main {

    // *******************************************************
    // 1. 直接暴力求解
    public ListNode removeNthFromEnd1(ListNode head, int n) {

        // 定义一个新的节点, 来记录原链表的头节点的位置
        ListNode newHead = new ListNode(0);
        newHead.next = head;

        // 为了让原题目的 head 节点所带代表的意思不发生变化, 我们新建立一个节点用来代替 hed 行驶他的职责
        ListNode cur = head;

        // 链表长度
        int len = 0;

        // 求链表长度
        while (cur != null) {
            cur = cur.next;
            len++;
        }
        // 这里 cur 的工作就完成了


        // 求出我们要删除节点的正序位置
        int dest = len - n;

        // 重新给 cur 赋值, 让他继续打一份工 (万恶的资本家)
        cur = newHead;

        // 遍历到需要删除的节点的前一个节点
        for (int i = 0; i < dest; i++) {
            cur = cur.next;
        }

        // 记录要删除的节点的前一个位置
        ListNode prev = cur;

        // cur 继续遍历, 直接跳过要删除的节点, 记录下要删除节点的后面一个节点
        cur = cur.next.next;

        // 删除节点, 只需要将这两个节点连接起来就行了
        prev.next = cur;

        // 返回原链表的头结点, 这里就可以看出来我们定义 newHead 节点的好处了, 因为我们如果是直接返回 head 的话, 肯定是会出错的
        // 因为我们如果删除的是头结点, 也就是第一个节点, 你看他会不会出错
        return newHead.next;
    }

    // **************************************************
    // 2. 一遍遍历就删除
    public ListNode removeNthFromEnd(ListNode head, int n) {

        // 定义虚拟节点
        ListNode newHead = new ListNode(1);
        newHead.next = head;

        // 打工仔
        ListNode fast = newHead;

        // 目标
        ListNode slow = newHead;

        // 因为我们需要知道的是要删除节点的前一个节点, 所以我们要特别注意 fast离 slow距离
        //也就是 fast为 null时 slow要走到 要删节点的前一个节点, 也就是距离 fast有 n个节
        // 点的位置, 加上 fast自已的, 他们要差上 n + 1
        // 让 fast先走上 n + 1步
        for (int i = 0; i < n + 1; i++) {
            fast = fast.next;
        }

        // 让 fast 走到 null, 此时, slow 也就走到要删除节点的前一个位置
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // 连接要删除节点的旁边两个节点
        slow.next = slow.next.next;

        // 返回结果
        return newHead.next;
    }


    static class ListNode {

        int val;

        ListNode next;

        ListNode() {

        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val; this.next = next;
        }

    }
}